class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public class Solution {
    public ListNode reverseList(ListNode head) {
        int length = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            length++;
        }
        if(length == 0) {
            return null;
        }
        ListNode[] listNodes = new ListNode[length];
        cur = head;
        for(int i = 0; i < length; i++) {
            listNodes[i] = cur;
            cur = cur.next;
        }
        ListNode new_head = listNodes[length-1];
        ListNode result = new_head;
        for(int i = length-2; i >= 0; i--) {
            new_head.next = listNodes[i];
            new_head = new_head.next;
        }
        new_head.next = null;
        return result;
    }

}
